The present invention relates to content addressable memory (CAM). In particular, the present invention relates to a priority encoder and method for high speed encoding of input data signals into addresses in accordance with predetermined priorities.
In many conventional memory systems, such as random access memory, binary digits (bits) are stored in memory cells, and are accessed by a processor that specifies a linear address that is associated with the given cell. This system provides rapid access to any portion of the memory system within certain limitations. To facilitate processor control, each operation that accesses memory must declare, as a part of the instruction, the address of the memory cell/cells required. Standard memory systems are not well designed for a content based search. Content based searches in standard memory require software based algorithmic search under the control of the microprocessor. Many memory operations are required to perform a search. These searches are neither quick nor efficient in using processor resources.
To overcome these inadequacies an associative memory system called Content Addressable Memory (CAM) has been developed. CAM allows cells to be referenced by their contents, so it has first found use in lookup table implementations such as cache memory subsystems and is now rapidly finding use in networking systems. CAM""s most valuable feature is its ability to perform a search and compare of multiple locations as a single operation, in which search data is compared with data stored within the CAM. Typically search data is loaded onto search lines and compared with stored words in the CAM. During a search-and-compare operation, a match or mismatch signal associated with each stored word is generated on a matchline, indicating whether the search word matches a stored word or not.
A typical CAM block diagram is shown in FIG. 1. The CAM 10 includes a matrix, or array 100, of CAM cells (not shown) arranged in rows and columns. For a ternary CAM, the cells are typically either DRAM or SRAM type, and store one of three states: logic xe2x80x9c1xe2x80x9d, logic xe2x80x9c0xe2x80x9d and xe2x80x9cdon""t carexe2x80x9d, as two bits of data. An array of DRAM based ternary CAM cells, as described in Canadian Patent Application No. 2,266,062, filed Mar. 31, 1999, the contents of which are incorporated herein by reference, have the advantage of occupying significantly less silicon area than their SRAM based counterparts. The description of the operation of the ternary DRAM cell is detailed in the aforementioned reference. A predetermined number of CAM cells in a row store a word of data. An address decoder 12 is used to select any row within the CAM array 100 to allow data to be written into or read out of the selected row. Although most commonly, data is written or loaded into the CAM and searched. Data access circuitry such as bitlines and column selection devices, are located within the array 100 to transfer data into and out of the array 100. Located within CAM array 100 for each row of CAM cells are matchline sense circuits (not shown) used for search-and-compare operations. The various registers 15 receive and hold data from the data I/O block 20 for search-and-compare operations, and other components of the CAM include the control circuit block 14, the flag logic block 16, the voltage supply generation block 18, various control and address registers 22, refresh counter 28 and JTAG block 24.
The matchline sense circuits are used during search-and-compare operations for outputting a result indicating a successful or unsuccessful match of a search word against the stored word in the row. The results for all rows are processed by the priority encoder 200 to output the address (Match Address) corresponding to the location of a matched word. The match address is stored in match address registers 25 before being output by the match address output block 26. The generation of the match address is relatively simple when there is only one stored word which matches the search word. However, when there are many stored words matching the search word, the priority encoder is still limited to provide only one match address. Hence, a rule is applied in which only the highest priority matching word is accepted, and all lesser priority matching words are ignored. Within the context of CAM""s, the highest priority matching word is located at the lowest physical address in the CAM array and accordingly, the lowest priority matching word is located at the highest physical address in the CAM array. For example, if two words located at binary address 0001 and 1001 match the search word, the word stored at binary address 0001 would have the highest priority. In general, the priority encoder 200 of the CAM is responsible for determining the highest priority matching word among many matching words, and generating the address corresponding to the highest priority matching word.
A more detailed block diagram of a typical priority encoder 200 is shown in FIG. 2. The priority encoder includes a mutliple match resolver block 204 and a ROM address decoder block 206 for generating an 8-bit address. Multiplexors 202 receive matchline sense output signals ML_OUT0 to ML_OUT255 from the matchline sense circuits, and an empty data signal EMPTY0 to EMPTY255. A common control signal SELECT EMPTY connected to each multiplexor 202 selects empty data for input to the multiple match resolver block 204 when active. However, for the purposes of the following discussion, it is assumed that SELECT EMPTY is inactive, and only the matchline sense output signals are passed to the multiple match resolver block 204. For each input of the multiple match resolver block 204, there is exactly one corresponding output 208 supplied to ROM decoder block 206. In general operation, when multiple match resolver block 204 receives one or more active ML_OUT signals, ie. when a match between the stored word in the CAM and search word occurs, multiple match resolver block 204 determines which stored word has the highest priority and activates the corresponding output signal 208. ROM block 206 then generates an 8-bit address corresponding to the active output signal 208. Although the input signals are arranged in sequential order, it is the logical order assigned to the physical connection of the signal within multiple match resolver block 204 which is significant. In other words, if it is understood that ML_OUT0 is the highest priority location and ML_OUT255 is the lowest priority location, then the ML_OUT inputs could be connected in any order as long as the internal connections within multiple match resolver block 204 are correspondingly assigned according to their logical priority.
A disadvantage with the scheme shown in FIG. 2 is the long duration of time required to produce the match address after the matchline sense output signals are presented to the multiple match resolver block 204. The delay in receiving the match address is approximately 12 ns, a significant amount of time which delays subsequent CAM operations. Most of this delay is contributed by the memory access operation of the ROM.
It is therefore desirable to provide a searchline control circuit capable of operating at high speed to improve CAM performance.
It is an object of the present invention to obviate or mitigate at least one disadvantage of the prior art. In particular, it is an object of the present invention to provide a high speed priority encoder circuit, a method of using such a circuit, and a content addressable memory using such a priority encoding circuit, that generates highest priority match addresses quickly.
In a first aspect, the present invention provides a priority encoder for generating an address of a highest priority active data signal. The priority encoder has a first stage for receiving a plurality of active data signals, and generates at least one flag signal and at least one first address portion corresponding to at least one active data signal. The priority encoder includes a second stage for receiving the at least one flag signal in a logical order of priority for generating a second address portion corresponding to a highest priority flag signal. The second stage also enables passage of its corresponding first address portion from the first stage.
In an embodiment of the present invention, the first stage of the priority encoder includes a plurality of multiple match resolver circuits. Each multiple match resolver circuit of the first stage receives a set of the plurality of active data signals for generating the at least one flag signal and the first address portion corresponding to the highest priority active data signal. In a presently preferred embodiment, the at least one flag signal is one of a row and a column flag signal, and each multiple match resolver circuit is connected to common address lines for transferring the first address portion. The set of the plurality of active data signals includes 2 n active data signals, and the first address portion is n bits wide, where n is an integer greater than 0. In the presently preferred embodiment, the second stage includes at least one multiple match resolver circuit. The at least one multiple match resolver circuit receives at least one of the at least one flag signals for generating the second address portion corresponding to the highest priority flag signal.
In a further embodiment of the present invention, multiple match resolver circuits of the first stage are arranged as rows and columns in a logical order of priority, and the second stage is formed as a substantial column and row at approximately the centre of the rows and columns of multiple match resolver circuits respectively.
In yet another embodiment of the present invention, the second stage includes flag processing logic. The flag processing logic includes row priority logic and column priority logic for generating at least one row control signal and at least one column control signal corresponding to the at least one flag signal respectively. Additionally, the flag processing logic decodes the at least one row control signal and at least one column control signal to provide the second address portion. The column priority logic includes an address selection circuit for passing the first address portion corresponding to the highest priority column control signal.
In yet another embodiment of the present invention, each of the multiple match resolver circuits includes a control circuit. The control circuit overwrites the first address portion and the column flag signal in response to the row flag signal corresponding to the highest priority active data signal, such that the overwritten first address portion and the overwritten column flag signal are low logic levels.
A further aspect of the present invention provides a content addressable memory. The content addressable memory consists of an array of content addressable memory cells arranged in rows and columns, an address decoder for addressing rows of cells, write data circuitry for writing data to the cells, matchline sense circuitry for comparing the data stored in the cells with search data to provide active matchline sense output signals indicative of a match, and a priority encoder circuit for providing an address corresponding to the highest priority active matchline sense output signal. The priority encoder circuit further consists of a first stage for receiving the active matchline sense output signals in a logical order of priority. The first stage generates at least one flag signal and at least one first address portion corresponding to at least one active matchline sense output signal. The priority encoder circuit finally includes a second stage for receiving the at least one flag signal in a logical order of priority, and for generating a second address portion corresponding to a highest priority flag, and for enabling passage of its corresponding first address portion from the first stage.
In a further aspect of the present invention, there is provided a method for determining an address of a highest priority data signal from a plurality of data signals. The method consists of providing sets of data signals in a predetermined order of priority to a first stage priority encoder, resolving the highest priority data signal from each set of the data signals and generating lower significant bits of the address and flags corresponding to the highest priority data signals from each set of the data signals, resolving the highest priority flag of the flags in a second stage priority encoder for generating higher significant bits of the address, providing the lower significant bits of the address corresponding to the highest priority flag, and concatenating the lower significant bits of the address corresponding to the highest priority flag with the higher significant bits of the address to provide the address of the highest priority data signal. The step of resolving the highest priority data signal can include a step for generating row and column flags. The step of providing the lower significant bits of the address can include the step of setting the lower significant bits of the address corresponding to all lower priority flags to zero. The step of resolving the highest priority flag can include a step of generating an enable signal for allowing passage of the lower significant bits of the address corresponding to the highest priority flag.
A further aspect of the present invention provides a priority encoder for generating an address of a highest priority active data signal. The priority encoder consists of a plurality of multiple match resolver circuits arranged in rows and columns. Each multiple match resolver circuit receives a plurality of active data signals and generates a lower significant address corresponding to the highest priority active data signal, a row flag, and a column flag. The priority encoder also includes row priority logic associated with each row of multiple match resolver circuits for receiving the row flags, and for generating row control signals corresponding to the row having the highest priority row flag. The row control signals are operatively connected to the multiple match resolver circuits for inhibiting generation of the column flags and lower significant addresses corresponding to lesser priority rows The priority encoder further includes column priority logic associated with each column of multiple match resolver circuits and an address encoder. The column priority logic receives the column flags and lower significant addresses, and generates column control signals corresponding to the column having the highest priority column flag. The column control signals are operatively connected for inhibiting generation of the lower significant addresses corresponding to lesser priority columns and for generating the lower significant address corresponding to the highest priority column. The address encoder receives the row and column control signals and generates a higher significant address.